package features.advance.leetcode.interview.offer.medium;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 *  剑指 Offer 20. 表示数值的字符串
 *
 *  难度：中等
 *
 * 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
 * 数值（按顺序）可以分成以下几个部分：
 *
 *  1、若干空格
 *  2、一个 小数 或者 整数
 *  3、（可选）一个 'e' 或 'E' ，后面跟着一个 整数
 *  4、若干空格
 *
 * 小数（按顺序）可以分成以下几个部分：
 *
 *  1、（可选）一个符号字符（'+' 或 '-'）
 *  2、下述格式之一：
 *      1、至少一位数字，后面跟着一个点 '.'
 *      2、至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
 *      3、 一个点 '.' ，后面跟着至少一位数字
 *
 * 整数（按顺序）可以分成以下几个部分：
 *
 *  1、（可选）一个符号字符（'+' 或 '-'）
 *  2、至少一位数字
 *
 * 部分数值列举如下：
 *      ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
 * 部分非数值列举如下：
 *      ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
 *
 * 示例 1：
 *
 * 输入：s = "0"
 * 输出：true
 * 示例 2：
 *
 * 输入：s = "e"
 * 输出：false
 * 示例 3：
 *
 * 输入：s = "."
 * 输出：false
 * 示例 4：
 *
 * 输入：s = "    .1  "
 * 输出：true
 *
 * 提示：
 *
 * 1 <= s.length <= 20
 * s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。
 *
 * @author LIN
 * @date 2021-05-17
 */
public class Offer20 {
    enum State {
        STATE_INITIAL,
        STATE_INT_SIGN,
        STATE_INTEGER,
        STATE_POINT,
        STATE_POINT_WITHOUT_INT,
        STATE_FRACTION,
        STATE_EXP,
        STATE_EXP_SIGN,
        STATE_EXP_NUMBER,
        STATE_END,
    }

    enum CharType {
        CHAR_NUMBER,
        CHAR_EXP,
        CHAR_POINT,
        CHAR_SIGN,
        CHAR_SPACE,
        CHAR_ILLEGAL,
    }

    public CharType toCharType(char ch) {
        if (ch >= '0' && ch <= '9') {
            return CharType.CHAR_NUMBER;
        } else if (ch == 'e' || ch == 'E') {
            return CharType.CHAR_EXP;
        } else if (ch == '.') {
            return CharType.CHAR_POINT;
        } else if (ch == '+' || ch == '-') {
            return CharType.CHAR_SIGN;
        } else if (ch == ' ') {
            return CharType.CHAR_SPACE;
        } else {
            return CharType.CHAR_ILLEGAL;
        }
    }


    /**
     * 解题思路：循环判断，由于有多种状态，判断起来有难度
     *
     * 题解：确定有限状态自动机
     * @param s
     * @return
     */
    public boolean isNumber(String s) {
        Map<State, Map<CharType, State>> transfer = new HashMap<State, Map<CharType, State>>();
        Map<CharType, State> initialMap = new HashMap<CharType, State>(16) {{
            /*
            空格->初始状态
            数字->数字状态
            小数点->只有小数点状态
            正负号->整数符号
             */
            put(CharType.CHAR_SPACE, State.STATE_INITIAL);
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
            put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
        }};
        transfer.put(State.STATE_INITIAL, initialMap);
        Map<CharType, State> intSignMap = new HashMap<CharType, State>(16) {{
            /*
            数字->数字状态
            小数点->只有小数点状态
             */
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
        }};
        transfer.put(State.STATE_INT_SIGN, intSignMap);
        Map<CharType, State> integerMap = new HashMap<CharType, State>(16) {{
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_POINT, State.STATE_POINT);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_INTEGER, integerMap);
        Map<CharType, State> pointMap = new HashMap<CharType, State>(16) {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_POINT, pointMap);
        Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>(16) {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
        }};
        transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);
        Map<CharType, State> fractionMap = new HashMap<CharType, State>(16) {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_FRACTION, fractionMap);
        Map<CharType, State> expMap = new HashMap<CharType, State>(16) {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
            put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
        }};
        transfer.put(State.STATE_EXP, expMap);
        Map<CharType, State> expSignMap = new HashMap<CharType, State>(16) {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
        }};
        transfer.put(State.STATE_EXP_SIGN, expSignMap);
        Map<CharType, State> expNumberMap = new HashMap<CharType, State>(16) {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_EXP_NUMBER, expNumberMap);
        Map<CharType, State> endMap = new HashMap<CharType, State>(16) {{
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_END, endMap);

        int length = s.length();
        State state = State.STATE_INITIAL;

        for (int i = 0; i < length; i++) {
            CharType type = toCharType(s.charAt(i));
            if (!transfer.get(state).containsKey(type)) {
                return false;
            } else {
                state = transfer.get(state).get(type);
            }
        }
        return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
    }



    /**
     * 获取公式的后缀表达式，公式本身就是个树的中缀表达式
     * @param exp
     * @return
     */
    public static Stack<String> getBackOprExp(String exp) {
        Stack<String> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        try {
            char[] c = exp.toCharArray();
            StringBuilder buf = new StringBuilder();
            for (int i=0; i<c.length; i++) {
                if (c[i] == ' ') {
                    continue;
                } else if ("+-*/()".indexOf(c[i]) < 0) {
                    buf.append(c[i]);
                } else {
                    if (buf.length() > 0) {
                        s1.push(buf.toString());
                        buf.delete(0,  buf.length());
                    }
                    switch (c[i]) {
                        case '+':
                        case '-':
                            while(s2.size() > 0 && "*/".contains(s2.peek())) {
                                s1.push(s2.pop());
                            }
                            s2.push(String.valueOf(c[i]));
                            break;
                        case '*':
                        case '/':
                        case '(':
                            s2.push(String.valueOf(c[i]));
                            break;
                        case ')':
                            while (s2.size() > 0 && !"(".equals(s2.peek())) {
                                s1.push(s2.pop());
                            }
                            s2.pop();
                            break;
                    }
                }
            }
            if (buf.length() > 0) {
                s1.push(buf.toString());
            }
            while (s2.size() > 0) {
                s1.push(s2.pop());
            }
            while (s1.size() > 0) {
                s2.push(s1.pop());
            }
        } catch (Throwable e) {
            e.printStackTrace();
        }

        return s2;
    }


    public static void main(String[] args) {
        String s = "12e+5";

        Offer20 offer20 = new Offer20() {
        };
        boolean number = offer20.isNumber(s);
        System.out.println(number);
    }


}
